# 1 1 2 3 5 8 ....
# F(n)=F(n-1)+F(n-2)  F(0)=1 F(1)=1

def fib1(n):  # 时间复杂度O(2^n)
    if n == 0 or n == 1:
        return 1
    else:
        return fib1(n - 1) + fib1(n - 2)


def fib2(n):  # 时间复杂度O(n)，但是空间复杂度也会上升，导致空间浪费
    li = [1, 1]
    for i in range(2, n + 1):
        li.append(li[-1] + li[-2])
    return li[n]


def fib3(n):  # 时间复杂度O(n)，空间复杂度O(1)
    a, b = 1, 1
    c = 0
    if n == 0 or n == 1:
        return 1
    else:
        for i in range(2, n + 1):
            c = a + b
            a = b
            b = c
        return c


n = int(input("输入n："))
print(fib3(n))


"""
面试题：一段有n个台阶组成的楼梯，小明从楼梯的最底层向最高处前进，
它可以选择一次迈一阶或者一次迈两阶。
问：有多少种不同走法？

解：斐波那契数列
"""
